#!/usr/bin/env python
#
# Copyright 2007 Google Inc.
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#

import wsgiref.handlers
from google.appengine.ext import webapp

import cgi
import logging
import math
import wordstore

def ParseBoard(board):
  """Parse an incoming square board.
  
  Args:
    board: A string of the board with all rows/columns concatenated
  
  Returns:
    a tuple of (the size of the board, the board as an integer array)"""
  
  board = board.strip().lower()  # Normalize board contents
  size = math.sqrt(len(board))
  
  if int(size)**2 != size**2:
    raise ValueError('Board was not an integer square size.')
  if size > 6:
    # TODO(wac): Figure out if this is as bad as it seems.
    raise OverflowError('Board was over 5x5.')
  
  int_board = [wordstore.IdxFromChar(x) for x in board]
  
  return (int(size), int_board)

def SolvePartial(x, y, size, board, walk, seen=None):
  """Solve the part boggle board anchored at a specific location.
  
  Args:
    x: the X axis location to search from
    y: the Y axis location to search from
    size: the dimension of the board square
    board: the board as a single string 
    walk: the wordstore object being used to conduct the solver walk
    seen: a dictionary of whether we've been at a given cell before.
  """
  # Mark that we've been here
  if not seen:
    seen = [False]*(size**2)
  else:
    # Copy seen so that our changes don't leak up the callstack
    seen = seen[:]
  seen[y*size + x] = True
  words_found = []
  links_walked = 0
  # First see if we landed on a word
  if walk.wordstore is not None and walk.wordstore.get('word'):
    # Build a string of what we touched to get here
    touched = ','.join([str(i) for i in xrange(len(seen)) if seen[i]])
    words_found.append([walk.wordstore['word'], touched])

  # Now walk in the 8 cardinal directions where able
  for move_x, move_y in ((-1,-1), (-1,0), (-1,1),
                         (0,-1), (0,1),  # (0,0) is not a valid move
                         (1,-1), (1,0), (1,1)):
    new_x = x+move_x
    new_y = y+move_y
    # Take care of the move off-the-board cases
    if new_x < 0 or new_x >= size or new_y < 0 or new_y >= size:
      continue
    # Make sure we haven't been there before
    new_pos = new_y*size + new_x
    if seen[new_pos]:
      continue
    # Now look at next character
    new_walk = walk.DescendInt(board[new_pos])
    if not new_walk:  # Make sure there is the possibility of a word
      continue
    if board[new_pos] == 16:  # Special case for Q -> QU
      new_walk = new_walk.DescendInt(20)
      if not new_walk:  # Make sure there is the possibility of a word
        continue
    links_walked += 1
    words_found.extend(
        SolvePartial(new_x, new_y, size, board, new_walk, seen))
  return words_found

class SolvePartialHandler(webapp.RequestHandler):
  def get(self):
    size, board = ParseBoard(self.request.get('board'))
    x = int(self.request.get('x'))
    y = int(self.request.get('y'))
    if x < 0 or x >= size or y < 0 or y >= size:
      self.response.set_status(400, 'Invalid position for board size.')
      self.response.out.write('Invalid position for board size.')
      return
    final_words = set()
    walk = wordstore.WordStoreWalk().DescendInt(board[y*size + x])
    if board[y*size + x] == 16:  # Special case for Q -> QU
      walk = walk.DescendInt(20)
      if not walk:  # Make sure there is the possibility of a word
        self.response.out.write('[  ]')
        return

    final_words = SolvePartial(x, y, size, board, walk)
    self.response.out.write('[')
    for word in sorted(final_words, lambda a,b: len(b[0])-len(a[0])):
      if len(word[0]) >= 3:  # Boggle rules say 3+ letter words only
        self.response.out.write('["%s",[%s]],' % (word[0],word[1]))
    self.response.out.write(']')

### Administrative Handlers
class DumpWordsHandler(webapp.RequestHandler):
  def get(self):
    self.response.out.write(wordstore.DumpPrefix(self.request.query_string))

class WriteEmptyTrigrams(webapp.RequestHandler):
  def get(self):
    wordstore.WriteBadTrigrams()
    self.response.out.write(wordstore.DumpPrefix(self.request.query_string))

class AddWordsHandler(webapp.RequestHandler):
  def get(self):
    word = self.request.get('word')
    if not word:
      self.response.set_status(405, 'POST required for this URL.')
      self.response.out.write('I expected a post of words...')
    wordstore.AddWord(word)
    self.response.out.write('%s added.' % cgi.escape(word))

  def post(self):
    word_count = 0
    for word in self.request.body_file:
      word = word.strip().lower()
      if not word:
        continue
      wordstore.AddWord(word)
      word_count += 1
      if word_count % 250 == 0:
        logging.debug("Added %d words" % word_count)
    logging.debug("Flushing %d words into datastore" % word_count)
    
    wordstore.FlushChanges()


def main():
  application = webapp.WSGIApplication([
                                        ('/solve_partial', SolvePartialHandler),
                                        ('/addwords', AddWordsHandler),
                                        ('/dumpwords', DumpWordsHandler),
                                        ('/writeemptytrigrams',
                                         WriteEmptyTrigrams),
                                       ],
                                       debug=True)
  wsgiref.handlers.CGIHandler().run(application)


if __name__ == '__main__':
  main()
